package exercise;

// 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

import java.util.ArrayList;
import java.util.List;

// https://leetcode.cn/problems/generate-parentheses/
public class L230701_I {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();

        if (n == 0) {
            return new ArrayList<>();
        }
        dfs(n, n, ans, "");
        return ans;
    }

    /**
     *
     * @param left 左括号剩余数量
     * @param right 右括号剩余数量
     * @param ans 最终结果集
     * @param cur 当前结果
     */
    private void dfs(int left, int right, List<String> ans, String cur) {
        if (left == 0 && right == 0) {
            ans.add(cur);
            return;
        }

        // 左括号数量大于右括号, 剪枝
        if (left > right) {
            return;
        }

        if (left > 0) {
            dfs(left-1, right, ans, cur+"(");
        }

        if (right > 0) {
            dfs(left, right-1, ans, cur+")");
        }
    }

    public static void main(String[] args) {
        L230701_I s = new L230701_I();
        System.out.println(s.generateParenthesis(3));
    }
}
